package com.tys.algorithm.advanced.code.class14;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 输入：正数数组costs，正数数组profits，正数K，正数M
 * costs[i]表示i号项目的花费
 * profits[i]表示i号项目在扣除花费之后还能挣到的钱（利润）
 * K表示你只能串行的最多做K个项目
 * M表示你初始的资金
 * 说明：每做完一个项目，马上获得的收益，可以支持你去做下一个项目，不能并行的做项目
 * 输出：你最后获得的最大钱数
 */
public class Code04_IPO {

    // 最多K个项目
    // W是初始资金
    // 利润Profits[]， 花费Capital[] 一定等长
    // 返回最终最大的资金
    public static int findMaximizedCapital(int K, int W, int[] Profits, int[] Capital) {
        //小根堆：花费小
        PriorityQueue<Program> minCostQ = new PriorityQueue<>(new MinCostComparator());
        //大根堆：利润大
        PriorityQueue<Program> maxProfitQ = new PriorityQueue<>(new MaxProfitComparator());
        //将所有项目放入小根堆
        for (int i = 0; i < Profits.length; i++) {
            minCostQ.add(new Program(Profits[i], Capital[i]));
        }

        //k轮拿K个项目：可以做的最大项目数K
        for (int i = 0; i < K; i++) {
            //小根堆不为空，小根堆堆顶项目可以做
            while (!minCostQ.isEmpty() && minCostQ.peek().c <= W) {
                //弹出小根堆，放入大根堆
                maxProfitQ.add(minCostQ.poll());
            }
            //大根堆为空返回资金，做不够K个项目
            if (maxProfitQ.isEmpty()) {
                return W;
            }
            //大根堆弹出利润，提升总资金
            W += maxProfitQ.poll().p;
        }
        //做完所有K个项目
        return W;
    }

    public static class Program {
        public int p; //利润
        public int c; //花费

        public Program(int p, int c) {
            this.p = p;
            this.c = c;
        }
    }

    public static class MinCostComparator implements Comparator<Program> {

        @Override
        public int compare(Program o1, Program o2) {
            return o1.c - o2.c;
        }

    }

    public static class MaxProfitComparator implements Comparator<Program> {

        @Override
        public int compare(Program o1, Program o2) {
            return o2.p - o1.p;
        }

    }

}
